CS 5010: Problem Set 1

Out: Monday, September 15, 2014

Due: Monday, September 22, 2014 at 600pm

The goal of this problem set is to help you design functions that deal with finite data.

You must use the HtDP Beginning Student Language to solve the problems.

For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line

(require "extras.rkt")

(provide function)

(require rackunit)
(require "extras.rkt")

(provide
  initial-robot
  robot-left 
  robot-right
  robot-forward
  robot-north? 
  robot-south? 
  robot-east? 
  robot-west?) 

This will allow our testing framework to import your file and do automated testing on it.

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, code, and tests. You must also include the laboratory notebook.

1. You have taken a job at a robot factory. The robots your factory builds are circles of radius 15 that move around a 200 x 400 canvas room surrounded by a wall. (Watch the video of the Roomba). At every step, the robot can move forward or rotate 90 degrees either right or left. The robot can also sense when it has run into a wall.

   We will use graphics-style coordinates instead of standard mathematical coordinates. That is, (0,0) is the northwest corner of the canvas room. The x-coordinate increases as one goes east, and the y-coordinate increases as one goes south. So, the southeast corner is at (200,400).

   The robot may start at any position: entirely inside the canvas room, entirely outside the canvas room, or partly inside and partly outside (that is, on an edge or corner). We image that the walls or edges are one-way traps. So the robot can travel anywhere until it is entirely inside the canvas room. Once that happens, it cannot get out again.

   You are to write a file called robot.rkt that provides the following functions:

   initial-robot : Number Number Real Real-> Robot
   GIVEN: a set of (x,y) coordinates
   RETURNS: a robot with its center at those coordinates, facing north
   (up).
   
   robot-left : Robot -> Robot
   robot-right : Robot -> Robot
   GIVEN: a robot
   RETURNS: a robot like the original, but turned 90 degrees either left
   or right.
   
   robot-forward : Robot PosInt -> Robot
   GIVEN: a robot and a distance
   RETURNS: a robot like the given one, but moved forward by the
   specified number of pixels distance.  If moving forward the specified number of
   pixels distance would cause the robot to move from being
   entirely inside the canvas room to being even partially outside the canvas room,
   then the robot should stop at the wall.
   
   robot-north? : Robot -> Boolean
   robot-south? : Robot -> Boolean
   robot-east? : Robot -> Boolean
   robot-west? : Robot -> Boolean
   GIVEN: a robot
   ANSWERS: whether the robot is facing in the specified direction.
   

   Note: When the specification groups functions as we have done here, you need only write down the purpose statement once (as we have done here). If your design strategy is the same for all the functions, then you only have to write that down once. Of course your examples must cover all the functions.

   We will be doing automated testing of your solution. In order to see whether you have correctly provided the indicated functions, load a copy of ps01-robot-qualification-tests.rkt into your directory and run it. This file tests only that you have provided all the functions you are supposed to. Make sure your solution passes those tests before you turn in your problem set.

2. (Tiny Text Editor) Do exercise 73 (the function "edit") from Part I, section 5.6 of HtDP/2e.

   You are to write a file called editor.rkt that provides the following functions:

   make-editor
   editor-pre
   editor-post
   edit
   

   Note: for our purposes, we will consider KeyEvent to be a scalar data type, which can be decomposed using the Cases strategy. KeyEvent and key=? are defined in the 2htdp/universe module. Look in the Help Desk for details. You should require 2htdp/universe to import key=?. The same holds for the regular-expression problem below.

   We will be doing automated testing of your solution. In order to see whether you have correctly provided the indicated functions, load a copy of ps01-edit-tests.rkt into your directory and run it. This file tests only that you have provided all the functions you are supposed to. Make sure your solution passes those tests before you turn in your problem set.

3. A snack machine has two items: chocolate bars and carrot sticks. Thanks to the University's healthy-eating initiative, chocolate bars cost $1.75, but carrot sticks cost only $0.70. A customer may put any sequence of coins into the machine, and then select an item. If the customer has deposited enough money into the machine, and the machine is not out of the selected item, then the machine will dispense the requested item and return the customer's change (if any). Otherwise the machine does nothing. The customer may also press "release", in which case the machine will return all the money that the customer has put in during the current transaction.

   For example, the customer may put three 25-cent pieces into the machine. If he then selects the carrot sticks, the machine will dispense one package of carrot sticks and 5 cents in change. If he tries to select the chocolate bars instead, nothing will happen. (The customer must press "release" to get his money back. He may do that at any time.) If the customer puts two 25-cent pieces, a dime, and 3 nickels into the machine (in any order), the same things will happen. If the machine is out of the requested item, nothing happens; the customer must still press "release" to get his money back.

   The machine has a container, called the bank, that contains all the money it has kept from customers' purchases. The customer's money is added to the bank only after he or she has successfully made a purchase.

   The possible inputs from the customer are given by the following data definition:

   A CustomerInput is one of
   -- a positive Number PosInt interp: insert the specified number of cents
   -- "chocolate"       interp: request a chocolate bar
   -- "carrots"         interp: request a package of carrot sticks
   -- "release"         interp: return all the coins that the customer has put in
   

   You are to write a file called snacks.rkt that provides the following functions:

   initial-machine : Number Number NonNegInt NonNegInt-> Machine
   GIVEN: the number of chocolate bars and the number of packages of
   carrot sticks
   RETURNS: a machine loaded with the given number of chocolate bars and
   carrot sticks, with an empty bank.
   
   machine-next-state : Machine CustomerInput -> Machine
   GIVEN: a machine state and a customer input
   RETURNS: the state of the machine that should follow the customer's
   input
   
   machine-chocolates : Machine ->  Number NonNegInt
   GIVEN: a machine state
   RETURNS: the number of chocolate bars left in the machine
   
   machine-carrots : Machine ->  Number NonNegInt
   GIVEN: a machine state
   RETURNS: the number of packages of carrot sticks left in the machine
   
   machine-bank : Machine ->  Number NonNegInt
   GIVEN: a machine state
   RETURNS: the amount of money in the machine's bank, in cents
   

   We will be doing automated testing of your solution. In order to see whether you have correctly provided the indicated functions, load a copy of ps01-snacks-tests.rkt into your directory and run it. This file tests only that you have provided all the functions you are supposed to. Make sure your solution passes those tests before you turn in your problem set.

4. This exercise is based on Exercise 100 in HtDP/2e. As in that exercise, you are to design a set of functions that illustrate the workings of a finite-state machine for accepting strings that exactly match the regular expression

   (a | b)* (c | d)* e

   However, rather than having a graphical illustration, do the following: First, perform an information analysis and design the data representation for the states of your machine. You may wish to write down a state-transition diagram (like the ones here) to illustrate the meaning of your state. Keep your diagram as simple as possible. You should submit your state-transition diagram either as ascii art in your solution file, or as a jpg or pdf, created in your favorite graphics program.

   KeyEvents of length greater than 1 should be ignored, that is, any such KeyEvent should leave the machine's state unchanged. If the machine encounters a bad letter or a letter out of sequence, it should go to an error state. Once the machine is in an error state, it stays there on any input.

   Design the following functions and provide them in a file named regexp.rkt

   initial-state : Number -> State
   GIVEN: a number
   RETURNS: a representation of the initial state
   of your machine.  The given number is ignored.
   
   next-state : State KeyEvent -> State
   GIVEN: a state of the machine and a key event.
   RETURNS: the state that should follow the given key event.  A key
   event that is to be discarded should leave the state unchanged.
   
   accepting-state? : State -> Boolean
   GIVEN: a state of the machine
   RETURNS: true iff the given state is a final (accepting) state
   
   error-state? : State -> Boolean
   GIVEN: a state of the machine
   RETURNS: true iff the string seen so far does not match the specified
   regular expression and cannot possibly be extended to do so.
   

   You will need to provide a data definition for State. Be sure to write an interpretation for each state. For our purposes, we will consider KeyEvent to be a scalar data type, which can be decomposed using the Cases strategy.

   As with the other questions in this problem set, we will be doing automated testing of your solution. In order to see whether you have correctly provided the indicated functions, load a copy of ps01-regexp-tests.rkt into your directory and run it. This file tests only that you have provided all the functions you are supposed to. Make sure your solution passes those tests before you turn in your problem set.